#ifndef HOUYI_H_INCLUDED
#define HOUYI_H_INCLUDED
/******************************************************************************
* (c)2025 Michael T. Richter
*
* This software is distributed under the terms of WTFPLv2.  The full terms and
* text of the license can be found at http://www.wtfpl.net/txt/copying
******************************************************************************/
/*******************************************************************************
* HOUYI - Yet Another Robin Hood Hashtable implementation.
*
* https://programming.guide/robin-hood-hashing.html
*
* HOUYI is a single-header implementation of Robin Hood Hashing that features:
*
*   - fixed or variable sizing using simple callbacks
*   - user-customizable hash function (decently strong default provided)
*   - user-customizable dynamic memory allocation
*   - user-customizable key comparison
*   - optional user-supplied backing storage
*
* The target environment for this library is small embedded environments running
* either bare metal or in otherwise deterministic runtimes (like coroutines).
* As such there is no locking of components for thread safety.  If you need the
* locking with all the headache that entails, the Power of What The Fuck
* (WTFPLv2) enables you.
*
* For similar reasons of space management, the hash table does not store keys
* and values, but only pointers to them.  The application must keep values
* around in its own space, and keys must be similarly stored or must be created
* accurately on demand.  If you need the ability to store the keys and data
* directly inside the table, quite a bit more of the Power of What The Fuck
* will be needed.
*
* Iteration is very simple and currently supports a single iterator.  Any
* insertion or deletion during iteration invalidates the iterator leading to
* possible garbage results.  It is instead necessary to record desired changes
* during iteration and make those changes after the fact.  Iteration is callback
* based, so unless tools like coroutines, etc. are being used, all elements will
* be iterated over before execution of mainline code resumes.  To help with
* interfacing with (deterministic) concurrency systems, iteration is broken down
* into a "prep" phase (in which user data is associated with iteration) and the
* actual "iteration" phase (in which the user-supplied callback is repeatedly
* invoked).
*
* If this iteration does not suit your needs, the Power of What The Fuck will
* once again be needed.
*******************************************************************************/

#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

/*******************************************************************************
* MACRO AND CONSTANT DEFINITIONS
*******************************************************************************/

#define HOUYI_STORAGE_SIZE (sizeof(houyi_hash_t) + sizeof(size_t) + sizeof(void *) * 2)

#ifndef UNUSED
#define UNUSED(X) ((void)X)
#endif

/*******************************************************************************
* TYPE DEFINITIONS
*******************************************************************************/

/*
** Data type aliases for operations.
*/
typedef void *houyi_handle_t;
typedef void *houyi_iter_data_t;
typedef void *houyi_key_t;
typedef void *houyi_value_t;

typedef uint32_t houyi_hash_t;
typedef uint32_t houyi_seed_t;

typedef enum houyi_error_t {
    /* failure */
    HOUYI_FAIL    = 0,

    /* success codes */
    HOUYI_SUCCEED = 1,

    /* success-with-warning codes */
    HOUYI_LOAD_FACTOR   = -1,
    HOUYI_KEY_NOT_FOUND = -2,
} houyi_error_t;

/*
** Function footprints for callbacks and overrides.
*/

/* user-supplied key/value equality function */
typedef bool (*houyi_eq_func_t)(const void *, const void *, size_t);

/* user-supplied hash function */
typedef houyi_hash_t (*houyi_hash_func_t)(const void *, size_t, houyi_seed_t);

/* user-supplied iterator callback function */
typedef bool (*houyi_iterator_cb_t)(houyi_key_t, houyi_value_t, houyi_iter_data_t);

/***************************************
* A note on hash and comparison functions.
*
* In houyi a key or value size of 0 has a special meaning: it means that the key
* or value is a C NUL-terminated string.  The hash/comparison functions the user
* supplies must be written to conform to this.  This means that the hash function
* must adjust its local copy of the size parameter using `strlen()` and that the
* comparison would be better served comparing via the `strcmp()` family of
* functions than by the `memcmp()` functions.  Consult the implementation of the
* default hash and comparison functions for suggestions.
***************************************/

/* user-supplied memory allocation function */
typedef void *(*houyi_alloc_func_t)(size_t count, size_t size);

/* user-supplied memory deallocation function */
typedef void (*houyi_dealloc_func_t)(void *);

/* user-supplied error handling routine */
typedef void (*houyi_error_handler_t)(const char *file, const int line, const char *error_message);

/*
** Hash table initialization values.
**
** Sizes are for the values pointed at by the key and value pointers.
** If the key and value pointers are strings, the size should be
** HOUYI_STRING_SIZE to ensure handling is done properly.
**
** capacity -> maximum number of elements in table
** store    -> (OPTIONAL) memory store to use for the hash table; NULL for
**             dynamic fallocation; use HOUYI_STORAGE_SIZE() for minimum size
** seed     -> the table seed value to salt the hashes with
** skey     -> size of the key in bytes, 0 for a string
** svalue   -> size of the value in bytes, 0 for a string
** max_load -> the maximum load factor before warnings are returned on insertion
**             set to 0 for default (0.7)
** hasher   -> (OPTIONAL) user-supplied hash function, NULL for default
** fkeq     -> (OPTIONAL) user-supplied key equality check, NULL for default
** falloc   -> (OPTIONAL) user-supplied memory fallocation, NULL for default
** dealloc  -> (OPTIONAL) user-supplied memory deallocation, NULL for default
*/

typedef struct houyi_init_t
{
    size_t                capacity;
    void                 *store;
    houyi_seed_t          seed;
    size_t                skey;
    size_t                svalue;
    double                max_load;
    houyi_hash_func_t     hasher;
    houyi_eq_func_t       fkeq;
    houyi_alloc_func_t    falloc;
    houyi_dealloc_func_t  dealloc;
} houyi_init_t;

/*
** Some statistics for a table which can be used to tune usage.
**
** count           -> number of items now in the table
** capacity        -> maximum number of items possible in table
** load_factor     -> the current load factor of the table
** max_load_factor -> the maximum load factor before warnings are issued
** num_direct      -> number of elements placed straight in their hash slot
** mean_probe_len  -> mean probe length of table
** max_probe_len   -> max probe length of table
*/
typedef struct houyi_stats_t
{
    size_t count;
    size_t capacity;

    double load_factor;
    double max_load_factor;

    size_t num_direct;
    double mean_probe_len;
    size_t max_probe_len;
} houyi_stats_t;

/*******************************************************************************
* EXTERNAL LINKAGE
*******************************************************************************/

/*
** User-supplied error handler function.
*/
extern houyi_error_handler_t houyi_error_handler;

/*******************************************************************************
* PUBLIC API DECLARATIONS
*******************************************************************************/

/*
** Report the hash table capacity.
*/
size_t houyi_capacity(houyi_handle_t h);

/*
** Report the hash table element count.
*/
size_t houyi_count(houyi_handle_t h);

/*
** Delete a hash table.
**
** h -> the handle to an initialized hash table
**
** This will deallocate the store if it was dynamically allocated before
** deallocating the hash table metadata.  Using `h` after calling this
** function will *not* go well.
*/
void houyi_delete(houyi_handle_t h);

/*
** Checks a hash table for the existence of a key and returns its paired value.
**
** h     -> the handle of a hash table
** key   -> the key to search for
** value -> the value being returned
**
** Returns NULL in `value` and HOUYI_KEY_NOT_FOUND if the key is not in the
** table. Otherwise returns HOUYI_SUCCEED and places the paired value into
** `value`.  Any other problem results in NULL and HOUYI_FAIL.
*/
houyi_error_t houyi_get(houyi_handle_t h, houyi_key_t key, houyi_value_t *value);

/*
** Checks a hash table for the existence of a key.
**
** h   -> the handle of a hash table
** key -> the key to search for
**
** Returns HOUYI_FAIL if the key is not found and HOUYI_SUCCEED if it is.
*/
houyi_error_t houyi_has(houyi_handle_t h, houyi_key_t key);

/*
** Initialize a hash table.
**
** init -> initialization parameters, c.f. houyi_init_t comments for details
**
** Returns a handle to the hash table.
*/
houyi_handle_t houyi_init(houyi_init_t init);

/*
** Insert a value into the hash table.
**
** h     -> the handle to an initialized hash table
** key   -> a pointer to the key for the entry
** value -> a pointer to the value for the entry
**
** Returns `HOUYI_SUCCEED` if successful, `HOUYI_FAIL` on error, and
** HOUYI_LOAD_FACTOR (a warning, not an error) if the load factor exceeds the
** provided threshold after the insertion has been completed.
**
** Note that the table is fixed size.  If the insertion fails, the user will
** have to manually build a new table with a larger capacity and reshash.
** The helper function `houyi_rehash()` is supplied to make this easier.
*/
houyi_error_t houyi_insert(houyi_handle_t h, houyi_key_t key, houyi_value_t value);

/*
** Insert multiple values into the hash table.
**
** h     -> the handle to an initialized hash table
** key   -> an array of pointers to the keys for the entry
** value -> an array of pointers to the values for the entry
** count -> the number of key/value pairs
**
** Returns `HOUYI_SUCCEED` if successful, `HOUYI_FAIL` on error, and
** HOUYI_LOAD_FACTOR (a warning, not an error) if the load factor exceeds the
** provided threshold after the insertion has been completed.
**
** Note that the table is fixed size.  If the insertion fails, the user will
** have to manually build a new table with a larger capacity and reshash.
** The helper function `houyi_rehash()` is supplied to make this easier.
**
** It is up to the user to ensure that keys and values are paired in the proper
** number.
*/
houyi_error_t houyi_insert_batch(houyi_handle_t h, houyi_key_t *key, houyi_value_t *value, size_t count);

/*
** Prepare an iterator.
**
** h       -> the handle of the table to associate the data with
** context -> arbitrary data an application wishes to associate with iteration
**            this might be, for example, a coroutine handle for concurrency
*/
houyi_error_t houyi_iteration_prep(houyi_handle_t h, houyi_iter_data_t *context);

/*
** Iterate.
**
** h  -> the handle of the table to iterate
** cb -> the function to be called for each key/value element
**
** Returns HOUYI_FAIL if the handle or cb are invalid.  Returns HOUYI_SUCCEED
** otherwise.  If the callback returns "false" it means "don't stop".  If it
** returns "true" it means "stop iterating".
*/
houyi_error_t houyi_iterate(houyi_handle_t h, houyi_iterator_cb_t cb);

/*
** Calculate the load factor of the table.
*/
double houyi_load_factor(houyi_handle_t h);

/*
** Rehash all the key/value pairs of one table into another compatible table.
**
** hold -> the old table being rehashed
** hnew -> the new table receiving the new values
**
** Returns HOUYI_SUCCEED if the process worked and HOUYI_FAIL if it didn't.  On
** failure the destination table is in an unknown, possibly unstable state.  It
** should not be used and should instead be discarded.
*/
houyi_error_t houyi_rehash(houyi_handle_t hold, houyi_handle_t hnew);

/*
** Remove a value at a key, returning the value removed if present.
**
** h     -> the table from which to remove the key
** key   -> the key to remove from the table
** value -> the place to store the returned value (OPTIONAL, NULL if not needed)
**
** Returns HOUYI_SUCCEED if key found and removed, HOUYI_KEY_NOT_FOUND if the
** given key is not in the table, and HOUYI_FAIL if there is any kind of an
** other error.  The value pointer is optional and if passed NULL is ignored.
*/
houyi_error_t houyi_remove(houyi_handle_t h, houyi_key_t key, houyi_value_t *value);

/*
** Collect table statistics for tuning and performance monitoring.
*/
houyi_stats_t houyi_stats(houyi_handle_t h);

/*
** Reset a table as if newly-initialized.
**
** h -> the table to wipe
*/
void houyi_wipe(houyi_handle_t h);

#ifdef HOUYI_IMPLEMENTATION
/*******************************************************************************
* HOUYI IMPLEMENTATION SECTION
* ==============================
*
* In a single source file in your project, the symbol HOUYI_IMPLEMENTATION
* must be defined before including the header:
*
*   ```c
*   #define HOUYI_IMPLEMENTATION
*   #include "houyi.h"
*   ```
*
* All other source files using this library must *not* define this symbol.
*******************************************************************************/

/*******************************************************************************
* DEBUG AIDS
*******************************************************************************/

#ifdef HOUYI_DEBUG
#define NL()            printf("\n");
#define OUTPUT(M)       printf("DEBUG %s %d: %s\n", __FILE__, __LINE__, M)
#define OUTPUT_(M, ...) printf("DEBUG %s %d: " M "\n", __FILE__, __LINE__, __VA_ARGS__)
static void houyi_dump_table(houyi_handle_t h);
static void houyi_dump_stats(houyi_stats_t stats);
#else
#define NL()
#define OUTPUT(...)
#define OUTPUT_(...)
static inline void houyi_dump_table(houyi_handle_t h) {}
static inline void houyi_dump_stats(houyi_stats_t stats) {}
#endif //HOUYI_DEBUG

/*******************************************************************************
* IMPLEMENTATION DATA TYPES
*******************************************************************************/

typedef struct hy_table_t
{
    size_t                 capacity;
    houyi_hash_t          *hashes;
    size_t                *lprobes;
    void                 **keys;
    void                 **values;
    bool                   dynamic;
    size_t                 count;
    size_t                 skey;
    size_t                 svalue;
    uint32_t               seed;
    double                 max_load;
    houyi_hash_func_t      fhash;
    houyi_eq_func_t        fkeq;
    houyi_alloc_func_t     falloc;
    houyi_dealloc_func_t   fdealloc;
    houyi_iter_data_t      iterdata;
} hy_table_t;

/*******************************************************************************
* STATIC HELPER FUNCTION DECLARATIONS
*******************************************************************************/

static void hy_clear_record(hy_table_t *t, size_t idx);
static void hy_default_error_handler(const char *file, const int line, const char *error_message);
static bool hy_equals(const void *buf1, const void *buf2, size_t size);
static uint32_t hy_fnv1a32_hash(const void *data, size_t len, uint32_t seed);
static int hy_find_key(hy_table_t *t, houyi_key_t key);
static void hy_get_record(hy_table_t *t, size_t idx, houyi_hash_t *hash, size_t *lprobe, houyi_key_t *key, houyi_value_t *value);
static size_t hy_hash_to_index(uint32_t hash, size_t n);
static void hy_place_record(hy_table_t *t, size_t idx, houyi_hash_t hash, size_t lprobe, houyi_key_t key, houyi_value_t value);
static void hy_swap_record(hy_table_t *t, size_t idx, houyi_hash_t *hash, size_t *lprobe, houyi_key_t *key, houyi_value_t *value);

/*******************************************************************************
* GLOBAL VARIABLES
*******************************************************************************/

houyi_error_handler_t houyi_error_handler = hy_default_error_handler;

/*******************************************************************************
* PUBLIC API DEFINITIONS
*******************************************************************************/

size_t houyi_capacity(houyi_handle_t h)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return 0; }

    OUTPUT_("houyi_capacity(h = %p)", h);
    hy_table_t *t = h;
    return t ? t->capacity : 0;
}

size_t houyi_count(houyi_handle_t h)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return 0; }

    OUTPUT_("houyi_count(h = %p)", h);
    hy_table_t *t = h;
    return t ? t->count : 0;
}

void houyi_delete(houyi_handle_t h)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return; }

    OUTPUT_("houyi_delete(h = %p)", h);
    hy_table_t *t = h;
    if (t)
    {
        if (t->dynamic)
        {
            t->fdealloc(t->hashes);
            t->hashes = NULL;
            t->lprobes = NULL;
            t->keys = NULL;
            t->values = NULL;
        }
        t->fdealloc(t);
    }
}

houyi_error_t houyi_get(houyi_handle_t h, houyi_key_t key, houyi_value_t *value)
{
    if (h == NULL)     { houyi_error_handler(__FILE__, __LINE__, "NULL handle");          return HOUYI_FAIL; }
    if (key == NULL)   { houyi_error_handler(__FILE__, __LINE__, "NULL key");             return HOUYI_FAIL; }
    if (value == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL value reference"); return HOUYI_FAIL; }

    OUTPUT_("houyi_get(h = %p, key = %p, value = %p)", h, key, value);
    if (!h || !key || !value)
    {
        return HOUYI_FAIL;
    }
    else
    {
        hy_table_t *t = h;
        int idx = hy_find_key(h, key);
        if (idx != -1)
        {
            *value = t->values[idx];
        }
        return idx == -1 ? HOUYI_KEY_NOT_FOUND : HOUYI_SUCCEED;
    }
}

houyi_error_t houyi_has(houyi_handle_t h, houyi_key_t key)
{
    if (h == NULL)   { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return HOUYI_FAIL; }
    if (key == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL key");    return HOUYI_FAIL; }

    OUTPUT_("houyi_has(h = %p, key = %p)", h, key);
    return hy_find_key(h, key) == -1 ? HOUYI_FAIL : HOUYI_SUCCEED;
}

houyi_handle_t houyi_init(houyi_init_t init)
{
    OUTPUT_("houyi_get(&init = %p)", &init);
    hy_table_t *rv;
    if (init.capacity == 0)
    {
        houyi_error_handler(__FILE__, __LINE__, "zero-capacity hash table is nonsense");
        rv = NULL;
    }
    else
    {
        houyi_alloc_func_t alloc = init.falloc ? init.falloc : calloc;
        houyi_dealloc_func_t dealloc = init.dealloc ? init.dealloc : free;

        rv = alloc(1, sizeof(hy_table_t));
        if (rv != NULL)
        {
            uint8_t *store = init.store ? init.store : alloc(init.capacity, HOUYI_STORAGE_SIZE);
            memset(store, 0, init.capacity * HOUYI_STORAGE_SIZE);

            if (store == NULL)
            {
                houyi_error_handler(__FILE__, __LINE__, "could not allocate memory for store");
                dealloc(rv);
                rv = NULL;
            }
            else
            {
                rv->capacity = init.capacity;
                rv->hashes = (houyi_hash_t *)store;
                rv->lprobes = (size_t *)((uint8_t *)rv->hashes + (sizeof(houyi_hash_t) * init.capacity));
                rv->keys = (void **)((uint8_t *)rv->lprobes + (sizeof(size_t) * init.capacity));
                rv->values = (void **)((uint8_t *)rv->keys + (sizeof(void *) * init.capacity));
                if (store == init.store) { rv->dynamic = false;  }
                else                     { rv->dynamic = true; }
                rv->count = 0;
                rv->skey = init.skey;
                rv->svalue = init.svalue;
                rv->seed = init.seed;
                rv->max_load = init.max_load ? init.max_load : 0.7;
                rv->fhash = init.hasher ? init.hasher : hy_fnv1a32_hash;
                rv->fkeq = init.fkeq ? init.fkeq : hy_equals;
                rv->falloc = init.falloc ? init.falloc : calloc;
                rv->fdealloc = init.dealloc ? init.dealloc : free;
            }
        }
        else
        {
            houyi_error_handler(__FILE__, __LINE__, "unable to allocate space for table metadata");
        }
    }

#ifdef HOUYI_DEBUG
    UNUSED(houyi_dump_table);   /* kill an irritating warning */
#endif //HOUYI_DEBUG
    return rv;
}

houyi_error_t houyi_insert(houyi_handle_t h, houyi_key_t key, houyi_value_t value)
{
    OUTPUT_("houyi_insert(h = %p, key = %p, value = %p)", h, key, value);
    houyi_error_t rv = HOUYI_FAIL;
    hy_table_t *t = h;

    if ((h != NULL) && (key != NULL) && (value != NULL))
    {
        /* either there's room or we're replacing an existing value */
        if ((t->count < t->capacity) || (hy_find_key(t, key) != -1))
        {
            houyi_hash_t hash = t->fhash(key, t->skey, t->seed);
            size_t index = hy_hash_to_index(hash, t->capacity);
            size_t lprobe = 0;
            for (size_t i = 0; i < t->capacity; i++)
            {
                size_t idx = index + i;
                idx = idx < t->capacity ? idx : idx - t->capacity;

                /* we have an empty slot, fill it */
                if (!t->keys[idx])
                {
                    hy_place_record(t, idx, hash, lprobe, key, value);
                    t->count++;
                    rv = HOUYI_SUCCEED;
                    break;
                }
                else
                {
                    /* we are replacing a key */
                    if (t->fkeq(key, t->keys[idx], t->skey))
                    {
                        hy_place_record(t, idx, hash, lprobe, key, value);
                        /* DON'T increase the count! */
                        rv = HOUYI_SUCCEED;
                        break;
                    }
                    /* we found a rich bastard */
                    else if (t->lprobes[idx] < lprobe)
                    {
                        hy_swap_record(t, idx, &hash, &lprobe, &key, &value);
                        /* DON'T increase the count (yet)! */
                    }
                }
                ++lprobe;
            }
        }
        else
        {
            houyi_error_handler(__FILE__, __LINE__, "table full, cannot insert");
        }
    }
    else
    {
        houyi_error_handler(__FILE__, __LINE__, "handle, key and/or value are NULL");
    }

    if ((rv == HOUYI_SUCCEED) && (houyi_load_factor(h) >= t->max_load))
    {
        rv = HOUYI_LOAD_FACTOR;
    }

    return rv;
}

houyi_error_t houyi_insert_batch(houyi_handle_t h, houyi_key_t *keys, houyi_value_t *values, size_t count)
{
    if (h == NULL)     { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return HOUYI_FAIL; }
    if (keys == NULL)   { houyi_error_handler(__FILE__, __LINE__, "NULL keys");   return HOUYI_FAIL; }
    if (values == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL values"); return HOUYI_FAIL; }

    hy_table_t *t = h;

    for (size_t i = 0; i < count; i++)
    {
        if (keys[i]   == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL keys");   return HOUYI_FAIL; }
        if (values[i] == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL values"); return HOUYI_FAIL; }
    }

    return HOUYI_FAIL;
}

houyi_error_t houyi_iteration_prep(houyi_handle_t h, houyi_iter_data_t *context)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return HOUYI_FAIL; }

    hy_table_t *t = h;
    t->iterdata = context;

    return HOUYI_SUCCEED;
}

houyi_error_t houyi_iterate(houyi_handle_t h, houyi_iterator_cb_t cb)
{
    if (h == NULL)  { houyi_error_handler(__FILE__, __LINE__, "NULL handle");   return HOUYI_FAIL; }
    if (cb == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL callback"); return HOUYI_FAIL; }

    hy_table_t *t = h;

    for (size_t i = 0; i < t->capacity; i++)
    {
        if (t->keys[i] != NULL)
        {
            if (cb(t->keys[i], t->values[i], t->iterdata))
            {
                break;
            }
        }
    }

    return HOUYI_SUCCEED;
}

double houyi_load_factor(houyi_handle_t h)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return -1.0; }

    OUTPUT_("houyi_load_factor(h = %p)", h);
    hy_table_t *t = h;
    return (double)t->count / (double)t->capacity;
}

houyi_error_t houyi_rehash(houyi_handle_t hold, houyi_handle_t hnew)
{
    if (hold == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL old handle"); return HOUYI_FAIL; }
    if (hnew == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL new handle"); return HOUYI_FAIL; }

    OUTPUT_("houyi_rehash(hold = %p, hnew = %p)", hold, hnew);
    bool rv = HOUYI_SUCCEED;

    hy_table_t *told = hold;
    hy_table_t *tnew = hnew;

    if (told->count  <= (tnew->capacity - tnew->count) &&
        told->skey   == tnew->skey &&
        told->svalue == tnew->svalue)
    {
        for (size_t i = 0; i < told->capacity && rv != HOUYI_FAIL; i++)
        {
            if (told->keys[i])
            {
                houyi_error_t e = houyi_insert(hnew, told->keys[i], told->values[i]);
                if (e == HOUYI_FAIL)
                {
                    houyi_error_handler(__FILE__, __LINE__, "insertion failure while rehashing");
                    rv = e;
                }
                else if (e == HOUYI_LOAD_FACTOR)
                {
                    rv = e;
                }
            }
        }
    }
    else
    {
        houyi_error_handler(__FILE__, __LINE__, "incompatible tables for rehashing");
        rv = HOUYI_FAIL;
    }

    return rv;
}

houyi_error_t houyi_remove(houyi_handle_t h, houyi_key_t key, houyi_value_t *value)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return HOUYI_FAIL; }

    OUTPUT_("houyi_remove(h = %p, key = %p, value = %p)", h, key, value);
    houyi_error_t rv = HOUYI_FAIL;

    if (h && key)
    {
        hy_table_t *t = h;

        if (value) { *value = NULL; }
        int idx = hy_find_key(t, key);

        // key was not found
        if (idx == -1)
        {
            rv = HOUYI_KEY_NOT_FOUND;
        }
        // key was found
        else
        {
            if (value) { *value = t->values[idx]; }
            t->count--;
            rv = HOUYI_SUCCEED;
            for (size_t i = 0; i < t->capacity; i++)
            {
                /* which index are we deleting? */
                int d = idx + i     ; d -= (d >= t->capacity) ? t->capacity : 0;
                /* which index might we be moving */
                int m = idx + i + 1 ; m -= (m >= t->capacity) ? t->capacity : 0;

                /* delete the record */
                hy_clear_record(t, d);

                /* check the next record for the possibility of moving */
                houyi_hash_t hash = 0;
                size_t lprobe = 0;
                houyi_key_t key = NULL;
                houyi_value_t value = NULL;
                hy_get_record(t, m, &hash, &lprobe, &key, &value);
                if ((hash == 0) && (lprobe == 0) && (key == NULL) && (value == NULL))
                {
                    /* empty record found, so we have finished moving */
                    break;
                }
                else if (lprobe == 0)
                {
                    /* the record is already in its proper place */
                    break;
                }
                else
                {
                    lprobe--;
                    hy_place_record(t, d, hash, lprobe, key, value);
                }
            }
        }
    }

    return rv;
}

houyi_stats_t houyi_stats(houyi_handle_t h)
{
    houyi_stats_t rv;
    memset(&rv, 0, sizeof(rv));
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return rv; }

    OUTPUT_("houyi_stats(h = %p)", h);
    hy_table_t *t = h;

    rv.count = t->count;
    rv.capacity = t->capacity;

    rv.load_factor = houyi_load_factor(h);
    rv.max_load_factor = t->max_load;

    size_t direct = 0;
    double sum = 0.0;
    size_t max = 0;
    for (size_t i = 0; i < t->capacity; i++)
    {
        if (t->keys[i])
        {
            if (t->lprobes[i] == 0)
            {
                direct++;
            }
            sum += (double)t->lprobes[i];
            if (t->lprobes[i] > max)
            {
                max = t->lprobes[i];
            }
        }
    }
    rv.num_direct = direct;
    rv.mean_probe_len = sum / (double)(t->count ? t->count : 1);
    rv.max_probe_len = max;

    return rv;
}

void houyi_wipe(houyi_handle_t h)
{
    if (h == NULL) { houyi_error_handler(__FILE__, __LINE__, "NULL handle"); return; }
    OUTPUT_("houyi_wipe(h = %p)", h);

    hy_table_t *t = h;
    memset(t->hashes, 0, t->capacity * HOUYI_STORAGE_SIZE);
    t->count = 0;
}

/*******************************************************************************
* Static helper function definitions
*******************************************************************************/

static void hy_clear_record(hy_table_t *t, size_t idx)
{
    OUTPUT_("hy_clear_record(t = %p, size_t = %ld)", t, idx);
    t->hashes[idx] = 0;
    t->lprobes[idx] = 0;
    t->keys[idx] = NULL;
    t->values[idx] = NULL;
}

static bool hy_equals(const void *buf1, const void *buf2, size_t size)
{
    OUTPUT_("hy_equals(buf1 = %p, buf2 = %p, size = %ld)", buf1, buf2, size);
    /* size 0 means it's a string */
    if (size == 0)
    {
        return strcmp((const char *)buf1, (const char *)buf2) == 0;
    }
    /* anything else is fixed-size */
    else
    {
        return memcmp(buf1, buf2, size) == 0;
    }
}
static int hy_find_key(hy_table_t *t, houyi_key_t key)
{
    OUTPUT_("hy_clear_record(t = %p, key = %p)", t, key);
    int rv = -1;

    houyi_hash_t hash = t->fhash(key, t->skey, t->seed);
    size_t index = hy_hash_to_index(hash, t->capacity);
    for (size_t i = 0; i < t->capacity; i++)
    {
        size_t idx = index + i;
        idx = idx < t->capacity ? idx : idx - t->capacity;
        if (t->keys[idx])
        {
            if (t->fkeq(key, t->keys[idx], t->skey))
            {
                return idx;
                break;
            }
        }
        else
        {
            /* empty slot encountered; we can't be in the table */
            break;
        }
    }

    return rv;
}

#define FNV1A_PRIME  0x01000193U
#define FNV1A_OFFSET 0x811c9dc5U
static houyi_hash_t hy_fnv1a32_hash(const void *data, size_t len, uint32_t seed)
{
    OUTPUT_("hy_fnv2a32_hash(data = %p, len = %ld, seed = %08x)", data, len, seed);
    const unsigned char *p = (const unsigned char *)data;
    if (len == 0)
    {
        len = strlen(data);
    }

    // Start with the seed as the offset basis
    houyi_hash_t hash = (FNV1A_OFFSET ^ seed);
    for (size_t i = 0; i < len; i++)
    {
        hash ^= p[i];
        hash *= FNV1A_PRIME;
    }
    return hash;
}

static void hy_get_record(hy_table_t *t, size_t idx, houyi_hash_t *hash, size_t *lprobe, houyi_key_t *key, houyi_value_t *value)
{
    OUTPUT_("hy_get_record(t = %p, idx = %ld, hash = %p, lprobe = %p, key = %p, value = %p)", t, idx, hash, lprobe, key, value);
    *hash = t->hashes[idx];
    *lprobe = t->lprobes[idx];
    *key = t->keys[idx];
    *value = t->values[idx];
}

static size_t hy_hash_to_index(houyi_hash_t hash, size_t n)
{
    /*OUTPUT_("hy_hash_to_index(hash = %08x, n = %ld)", hash, n);*/
    /*this function is called very frequently and slows down debugging; enable at need*/
    return ((uint64_t)hash * (uint64_t)n) >> 32;
}

static void hy_place_record(hy_table_t *t, size_t idx, houyi_hash_t hash, size_t lprobe, houyi_key_t key, houyi_value_t value)
{
    OUTPUT_("hy_place_record(t = %p, idx = %ld, hash = %08x, lprobe = %ld, key = %p, value = %p)", t, idx, hash, lprobe, key, value);
    t->hashes[idx] = hash;
    t->lprobes[idx] = lprobe;
    t->keys[idx] = key;
    t->values[idx] = value;
}

static void hy_swap_record(hy_table_t *t, size_t idx, houyi_hash_t *hash, size_t *lprobe, void **key, void **value)
{
    OUTPUT_("hy_swap_record(t = %p, idx = %ld, hash = %p, lprobe = %p, key = %p, value = %p)", t, idx, hash, lprobe, key, value);
    houyi_hash_t h = t->hashes[idx];
    size_t l = t->lprobes[idx];
    void *k = t->keys[idx];
    void *v = t->values[idx];
    hy_place_record(t, idx, *hash, *lprobe, *key, *value);
    *hash = h;
    *lprobe = l;
    *key = k;
    *value = v;
}

static void hy_default_error_handler(const char *file, const int line, const char *error_message)
{
    printf("ERROR: %s(%d): %s\n", file, line, error_message);
}

#ifdef HOUYI_DEBUG
static void houyi_dump_table(houyi_handle_t h)
{
    hy_table_t *t = h;
    for (size_t i = 0; i < t->capacity; i++)
    {
        houyi_hash_t hash;
        size_t lprobe;
        houyi_key_t key;
        houyi_value_t value;
        hy_get_record(t, i, &hash, &lprobe, &key, &value);
        if ((hash == 0) && (lprobe == 0) && (key == NULL) && (value == NULL))
        {
            OUTPUT_("%3lu: **NULL RECORD**", i);
        }
        else
        {
            OUTPUT_("%3lu: hash = 0x%08x, lprobe = %-3ld, key = %-10s, value = %-10s",
                i, hash, lprobe, (char*)key, (char*)value);
        }
    }
}

static void houyi_dump_stats(houyi_stats_t stats)
{
    OUTPUT_("stats = {"
                "\n\t.count = %lu,"
                "\n\t.capacity = %lu,"
                "\n\n\t.load_factor = %f,"
                "\n\t.max_load_factor = %f,"
                "\n\n\t.num_direct = %lu,"
                "\n\t.mean_probe_len = %f,"
                "\n\t.max_probe_len = %lu,"
            "\n};",
            stats.count, stats.capacity,
            stats.load_factor, stats.max_load_factor,
            stats.num_direct, stats.mean_probe_len, stats.max_probe_len);
}
#endif

#endif //HOUYI_IMPLEMENTATION

#endif /*HOUYI_H_INCLUDED*/
